home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / gawk / cawf2st.zoo / regexp.c < prev    next >
C/C++ Source or Header  |  1992-04-12  |  40KB  |  1,223 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere
  3.  *
  4.  *      Copyright (c) 1986 by University of Toronto.
  5.  *      Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *      Permission is granted to anyone to use this software for any
  8.  *      purpose on any computer system, and to redistribute it freely,
  9.  *      subject to the following restrictions:
  10.  *
  11.  *      1. The author is not responsible for the consequences of use of
  12.  *              this software, no matter how awful, even if they arise
  13.  *              from defects in it.
  14.  *
  15.  *      2. The origin of this software must not be misrepresented, either
  16.  *              by explicit claim or by omission.
  17.  *
  18.  *      3. Altered versions must be plainly marked as such, and must not
  19.  *              be misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator
  22.  * precedence is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  */
  25. #include <stdio.h>
  26. #ifdef  UNIX
  27. #ifdef  USG
  28. #include <string.h>
  29. #else
  30. #include <strings.h>
  31. #endif
  32. #else
  33. #include <string.h>
  34. #endif
  35. #include "regexp.h"
  36. #include "regmagic.h"
  37.  
  38. /*
  39.  * The "internal use only" fields in regexp.h are present to pass info from
  40.  * compile to execute that permits the execute phase to run lots faster on
  41.  * simple cases.  They are:
  42.  *
  43.  * regstart     char that must begin a match; '\0' if none obvious
  44.  * reganch      is the match anchored (at beginning-of-line only)?
  45.  * regmust      string (pointer into program) that match must include, or NULL
  46.  * regmlen      length of regmust string
  47.  *
  48.  * Regstart and reganch permit very fast decisions on suitable starting points
  49.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  50.  * of lines that cannot possibly match.  The regmust tests are costly enough
  51.  * that regcomp() supplies a regmust only if the r.e. contains something
  52.  * potentially expensive (at present, the only such thing detected is * or +
  53.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  54.  * supplied because the test in regexec() needs it and regcomp() is computing
  55.  * it anyway.
  56.  */
  57.  
  58. /*
  59.  * Structure for regexp "program".  This is essentially a linear encoding
  60.  * of a nondeterministic finite-state machine (aka syntax charts or
  61.  * "railroad normal form" in parsing technology).  Each node is an opcode
  62.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  63.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  64.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  65.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  66.  * opposed to a collection of them) is never concatenated with anything
  67.  * because of operator precedence.)  The operand of some types of node is
  68.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  69.  * particular, the operand of a BRANCH node is the first node of the branch.
  70.  * (NB this is *not* a tree structure:  the tail of the branch connects
  71.  * to the thing following the set of BRANCHes.)  The opcodes are:
  72.  */
  73.  
  74. /* definition   number  opnd?   meaning */
  75. #define END     0       /* no   End of program. */
  76. #define BOL     1       /* no   Match "" at beginning of line. */
  77. #define EOL     2       /* no   Match "" at end of line. */
  78. #define ANY     3       /* no   Match any one character. */
  79. #define ANYOF   4       /* str  Match any character in this string. */
  80. #define ANYBUT  5       /* str  Match any character not in this string. */
  81. #define BRANCH  6       /* node Match this alternative, or the next... */
  82. #define BACK    7       /* no   Match "", "next" ptr points backward. */
  83. #define EXACTLY 8       /* str  Match this string. */
  84. #define NOTHING 9       /* no   Match empty string. */
  85. #define STAR    10      /* node Match this (simple) thing 0 or more times. */
  86. #define PLUS    11      /* node Match this (simple) thing 1 or more times. */
  87. #define OPEN    20      /* no   Mark this point in input as start of #n. */
  88.                         /*      OPEN+1 is number 1, etc. */
  89. #define CLOSE   30      /* no   Analogous to OPEN. */
  90.  
  91. /*
  92.  * Opcode notes:
  93.  *
  94.  * BRANCH       The set of branches constituting a single choice are hooked
  95.  *              together with their "next" pointers, since precedence prevents
  96.  *              anything being concatenated to any individual branch.  The
  97.  *              "next" pointer of the last BRANCH in a choice points to the
  98.  *              thing following the whole choice.  This is also where the
  99.  *              final "next" pointer of each individual branch points; each
  100.  *              branch starts with the operand node of a BRANCH node.
  101.  *
  102.  * BACK         Normal "next" pointers all implicitly point forward; BACK
  103.  *              exists to make loop structures possible.
  104.  *
  105.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  106.  *              BRANCH structures using BACK.  Simple cases (one character
  107.  *              per match) are implemented with STAR and PLUS for speed
  108.  *              and to minimize recursive plunges.
  109.  *
  110.  * OPEN,CLOSE   ...are numbered at compile time.
  111.  */
  112.  
  113. /*
  114.  * A node is one char of opcode followed by two chars of "next" pointer.
  115.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  116.  * value is a positive offset from the opcode of the node containing it.
  117.  * An operand, if any, simply follows the node.  (Note that much of the
  118.  * code generation knows about this implicit relationship.)
  119.  *
  120.  * Using two bytes for the "next" pointer is vast overkill for most things,
  121.  * but allows patterns to get big without disasters.
  122.  */
  123. #define OP(p)   (*(p))
  124. #define NEXT(p) (((*((p)+1)&0377)<<8) + *((p)+2)&0377)
  125. #define OPERAND(p)      ((p) + 3)
  126.  
  127. /*
  128.  * See regmagic.h for one further detail of program structure.
  129.  */
  130.  
  131.  
  132. /*
  133.  * Utility definitions.
  134.  */
  135. #ifndef CHARBITS
  136. #define UCHARAT(p)      ((int)*(unsigned char *)(p))
  137. #else
  138. #define UCHARAT(p)      ((int)*(p)&CHARBITS)
  139. #endif
  140.  
  141. #define FAIL(m) { regerror(m); return(NULL); }
  142. #define ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')
  143. #define META    "^$.[()|?+*\\"
  144.  
  145. /*
  146.  * Flags to be passed up and down.
  147.  */
  148. #define HASWIDTH        01      /* Known never to match null string. */
  149. #define SIMPLE          02      /* Simple enough to be STAR/PLUS operand. */
  150. #define SPSTART         04      /* Starts with * or +. */
  151. #define WORST           0       /* Worst case. */
  152.  
  153. /*
  154.  * Global work variables for regcomp().
  155.  */
  156. static char *regparse;          /* Input-scan pointer. */
  157. static int regnpar;             /* () count. */
  158. static char regdummy;
  159. static char *regcode;           /* Code-emit pointer; ®dummy = don't. */
  160. static long regsize;            /* Code size. */
  161.  
  162. /*
  163.  * Forward declarations for regcomp()'s friends.
  164.  */
  165. #ifndef STATIC
  166. #define STATIC  static
  167. #endif
  168. STATIC char *reg();
  169. STATIC char *regbranch();
  170. STATIC char *regpiece();
  171. STATIC char *regatom();
  172. STATIC char *regnode();
  173. STATIC char *regnext();
  174. STATIC void regc();
  175. STATIC void reginsert();
  176. STATIC void regtail();
  177. STATIC void regoptail();
  178. #ifdef STRCSPN
  179. STATIC int strcspn();
  180. #endif
  181.  
  182. /*
  183.  - regcomp - compile a regular expression into internal code
  184.  *
  185.  * We can't allocate space until we know how big the compiled form will be,
  186.  * but we can't compile it (and thus know how big it is) until we've got a
  187.  * place to put the code.  So we cheat:  we compile it twice, once with code
  188.  * generation turned off and size counting turned on, and once "for real".
  189.  * This also means that we don't allocate space until we are sure that the
  190.  * thing really will compile successfully, and we never have to move the
  191.  * code and thus invalidate pointers into it.  (Note that it has to be in
  192.  * one piece because free() must be able to free it all.)
  193.  *
  194.  * Beware that the optimization-preparation code in here knows about some
  195.  * of the structure of the compiled regexp.
  196.  */
  197. regexp *
  198. regcomp(exp)
  199. char *exp;
  200. {
  201.         register regexp *r;
  202.         register char *scan;
  203.         register char *longest;
  204.         register int len;
  205.         int flags;
  206.         extern char *malloc();
  207.  
  208.         if (exp == NULL)
  209.                 FAIL(